// https://leetcode.cn/problems/longest-increasing-subsequence/description/

// 算法思路总结：
// 1. 动态规划求最长递增子序列长度
// 2. dp[i]表示以nums[i]结尾的LIS长度
// 3. 双重循环比较前面所有较小元素
// 4. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return 1;

        vector<int> dp(m, 1);
        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 0 ; j < i ; j++)
            {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        int ret = 0;
        for (const int& num : dp)
            ret = max(ret, num);

        return ret;
    }
};

int main()
{
    vector<int> v1 = {10,9,2,5,3,7,101,18}, v2 = {0,1,0,3,2,3};
    Solution sol;

    cout << sol.lengthOfLIS(v1) << endl;
    cout << sol.lengthOfLIS(v2) << endl;

    return 0;
}